/*
 *  heap management in finsh shell.
 *
 * COPYRIGHT (C) 2006 - 2013, RT-Thread Development Team
 *
 *  This file is part of RT-Thread (http://www.rt-thread.org)
 *  Maintainer: bernard.xiong <bernard.xiong at gmail.com>
 *
 *  All rights reserved.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Change Logs:
 * Date           Author       Notes
 * 2010-03-22     Bernard      first version
 */
#include <finsh.h>

#include "finsh_var.h"

ALIGN(RT_ALIGN_SIZE)
uint8_t finsh_heap[FINSH_HEAP_MAX];
struct finsh_block_header {
	uint32_t length;
	struct finsh_block_header* next;
};
#define BLOCK_HEADER(x)                 (struct finsh_block_header*)(x)
#define finsh_block_get_header(data)    (struct finsh_block_header*)((uint8_t*)data - sizeof(struct finsh_block_header))
#define finsh_block_get_data(header)    (uint8_t*)((struct finsh_block_header*)header + 1)
#define HEAP_ALIGN_SIZE(size)           (((size) + HEAP_ALIGNMENT - 1) & ~(HEAP_ALIGNMENT-1))

static struct finsh_block_header* free_list;
static struct finsh_block_header* allocate_list;

static void finsh_heap_gc(void);

static void finsh_block_insert(struct finsh_block_header** list, struct finsh_block_header* header);
static void finsh_block_remove(struct finsh_block_header** list, struct finsh_block_header* header);
static void finsh_block_split(struct finsh_block_header* header, size_t size);
static void finsh_block_merge(struct finsh_block_header** list, struct finsh_block_header* header);

int finsh_heap_init(void)
{
	/* clear heap to zero */
	memset(&finsh_heap[0], 0, sizeof(finsh_heap));

	/* init free and alloc list */
	free_list           = BLOCK_HEADER(&finsh_heap[0]);
	free_list->length   = FINSH_HEAP_MAX - sizeof(struct finsh_block_header);
	free_list->next     = NULL;

	allocate_list       = NULL;

	return 0;
}

/**
 * allocate a block from heap
 */
void* finsh_heap_allocate(size_t size)
{
	struct finsh_block_header* header;

	size = HEAP_ALIGN_SIZE(size);

	/* find the first fit block */
	for(header = free_list;
	        ((header != NULL) && (header->length <= size + sizeof(struct finsh_block_header)));
	        header = header->next) ;

	if(header == NULL) {
		finsh_heap_gc();

		/* find the first fit block */
		for(header = free_list;
		        ((header != NULL) && (header->length < size + sizeof(struct finsh_block_header)));
		        header = header->next) ;

		/* there is no memory */
		if(header == NULL) return NULL;
	}

	/* split block */
	finsh_block_split(header, size);

	/* remove from free list */
	finsh_block_remove(&free_list, header);
	header->next = NULL;

	/* insert to allocate list */
	finsh_block_insert(&allocate_list, header);

	memset(finsh_block_get_data(header), 0, size);

	return finsh_block_get_data(header);
}

/**
 * release the allocated block
 */
void  finsh_heap_free(void* ptr)
{
	struct finsh_block_header* header;

	/* get block header */
	header = finsh_block_get_header(ptr);

	/* remove from allocate list */
	finsh_block_remove(&allocate_list, header);

	/* insert to free list */
	finsh_block_insert(&free_list, header);
	finsh_block_merge(&free_list, header);
}

/**
 * garbage collector
 */
static void finsh_heap_gc(void)
{
	int i;
	struct finsh_block_header* header, *temp;

	temp = NULL;

	/* find the first fit block */
	for(header = allocate_list; header != NULL;) {
		for(i = 0; i < FINSH_VARIABLE_MAX; i ++) {
			if(global_variable[i].type != finsh_type_unknown) {
				if(global_variable[i].value.ptr == finsh_block_get_data(header))
					break;
			}
		}

		temp   = header;
		header = header->next;

		/* this block is an unused block, release it */
		if(i == FINSH_VARIABLE_MAX) {
			finsh_heap_free(finsh_block_get_data(temp));
		}
	}
}

/**
 * insert a block to list
 */
void finsh_block_insert(struct finsh_block_header** list, struct finsh_block_header* header)
{
	struct finsh_block_header* node;

	if(*list == NULL) {
		*list = header;
		return;
	}

	/* find out insert point */
	node = *list;

	if(node > header) {
		/* insert node in the header of list */
		header->next = node;
		*list = header;

		return;
	} else {
		for(node = *list; node; node = node->next) {
			if(node->next > header) break;

			if(node->next == NULL) break;
		}
	}

	/* insert node */
	if(node->next != NULL) header->next = node->next;

	node->next      = header;
}

/**
 * remove block from list
 */
void finsh_block_remove(struct finsh_block_header** list, struct finsh_block_header* header)
{
	struct finsh_block_header* node;

	node = *list;

	if(node == header) {
		/* remove list header */
		*list = header->next;
		header->next = NULL;

		return;
	}

	for(node = *list; node != NULL; node = node->next) {
		if(node->next == header) {
			node->next = header->next;
			break;
		}
	}
}

/**
 * split block
 */
void finsh_block_split(struct finsh_block_header* header, size_t size)
{
	struct finsh_block_header* next;

	/*
	 * split header into two node:
	 * header->next->...
	 */
	next = BLOCK_HEADER((uint8_t*)header + sizeof(struct finsh_block_header) + size);
	next->length = header->length - sizeof(struct finsh_block_header) - size;
	header->length = size;
	next->next = header->next;

	header->next = next;
}

void finsh_block_merge(struct finsh_block_header** list, struct finsh_block_header* header)
{
	struct finsh_block_header* prev_node;
	struct finsh_block_header* next_node;

	next_node = header->next;

	if(*list == header) prev_node = NULL;
	else {
		/* find out the previous header */
		for(prev_node = *list; prev_node; prev_node = prev_node->next) {
			if(prev_node->next == header)
				break;
		}
	}

	/* try merge node */

	/* merge to previous node */
	if(prev_node != NULL &&
	        ((uint8_t*)prev_node + prev_node->length + sizeof(struct finsh_block_header)
	         == (uint8_t*)header)) {
		/* is it close to next node? */
		if((next_node != NULL) &&
		        ((uint8_t*)header + header->length + sizeof(struct finsh_block_header)
		         == (uint8_t*)next_node)) {
			/* merge three node */
			prev_node->length += header->length + next_node->length +
			                     2 * sizeof(struct finsh_block_header);

			prev_node->next = next_node->next;
		} else {
			prev_node->length += header->length + sizeof(struct finsh_block_header);
			prev_node->next = header->next;
		}
	} else /* merge to last node */
		if((next_node != NULL) &&
		        ((uint8_t*)header + header->length + sizeof(struct finsh_block_header)
		         == (uint8_t*)next_node)) {
			header->length += next_node->length + sizeof(struct finsh_block_header);
			header->next = next_node->next;
		}
}
